#include<iostream>
#include<fstream>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<new>
#include<cstring>
using namespace std;
typedef struct{
    int d;
    int* realV;// = (int*)malloc(sizeof(int) * 2 * d); 
    int* V;// = realV +  d;  
}Step;
#define ERROR 0
int Mysers_diff(vector<string> A, vector<string> B, int m, int n);
void find_path(int d, int m, int n, int kFinal, Step D[], vector<string> A, vector<string> B);
bool best_choice(int x1, int y1, int x2, int y2);  //用于判断最优路径中坐标的选择
void output_result(int x[], int y[], int n, vector<string> A, vector<string> B);
bool equal(vector<string> A, vector<string> B, int N);
int git_diff(string* option)
{
	//system("chcp 65001");
    int x = option[0].size(), y = option[1].size();
    char* filename1 = (char *)malloc(sizeof(char) * (x+1));
    char* filename2 = (char *)malloc(sizeof(char) * (y+1));
    strcpy(filename1, option[0].c_str()), strcpy(filename2, option[1].c_str());
    ifstream f1(filename1);
    ifstream f2(filename2);
    free(filename1), free(filename2);
    if(!f1 && !f2) return ERROR; 
    vector<string> file1, file2;
    string line;
    while (getline(f1, line))
        file1.push_back(line);
    while (getline(f2, line))
        file2.push_back(line);
    f1.close(), f2.close();
    int M = file1.size(), N = file2.size();
    if(M == N && equal(file1, file2, M))
        cout << "文件未进行更改" << endl;
    else
    {
    	int edit_times = Mysers_diff(file1, file2, M, N);
        cout <<"文件共出现" << edit_times << "次更改" << endl;
    }
	vector<string> ().swap(file1);
    vector<string> ().swap(file2);
    return 1;
}
int Mysers_diff(vector<string> A, vector<string> B, int m, int n)
{
    Step* D = (Step*)malloc(sizeof(Step)*(m+n));
    int *realV = new int[2*(m+n)];  //记录每条k线端点的x值
    int *V;
    V = realV + m + n, V[1] = 0;  //路径从（0，-1）点开始
    int d, k;  //d为走的路径数（对角线不算），k为对角线，其中y = x - k
    for(d = 0; d < m + n; d++)
    {
        D[d].d = d + 1;
        D[d].realV = (int*)malloc(sizeof(int)*(2*(d+1)));
        D[d].V = D[d].realV + d;
        for(k = -d; k <= d; k += 2)  //加2可保证k的奇偶性不变，根据已证明的定理，d的端点所在的k的奇偶性和d相同
        {
            bool down = (k == -d || (k != d && V[k-1] < V[k+1])); //k=-d时一定向下了，另种情况选择离终点最近的坐标
            int kPrev = down ? k + 1: k - 1;  //如果向下了，上一步所在的是k+1
            //上一个点
            int xStart = V[kPrev];
            int yStart = xStart - kPrev;
            //下一个点
            int xMid = down ? xStart : xStart + 1;
            int yMid = xMid - k;
            int xEnd = xMid;
            int yEnd = yMid;
            while (xEnd < m && yEnd < n && !A[xEnd].compare(B[yEnd]))
                xEnd++, yEnd++;
            V[k] = xEnd;
            D[d].V[k] = xEnd;
            if(xEnd >= m && yEnd >= n) //问题已经解决
            {   
                find_path(d, m, n, k, D, A, B); 
                return d;
            }
        }
    }
}
void find_path(int d, int m, int n, int kFinal, Step D[], vector<string> A, vector<string> B)
{
    int* x = (int*)malloc(sizeof(int)*(d+1));  //最优路径的坐标，按倒叙
    int* y = (int*)malloc(sizeof(int)*(d+1));
    int i = 0, kPrev = kFinal;
    x[i] = m, y[i] = n;
    while(d >= 1)
    {
        if(d == 1)
        {    
            i++;
            x[i] = 0, y[i] = 0;
            break;
        }
        if(kPrev+1 > d-1)
        {
            i++;
            x[i] = D[d-1].V[kPrev-1];
            y[i] = D[d-1].V[kPrev-1]+1-kPrev;
            kPrev = kPrev - 1;
        }
        else if (kPrev-1 < -d+1)
        {
            i++;
            x[i] = D[d-1].V[kPrev+1];
            y[i] = D[d-1].V[kPrev+1]-kPrev-1;
            kPrev = kPrev + 1;
        }
        
        else if(best_choice(D[d-1].V[kPrev+1], D[d-1].V[kPrev+1]-kPrev-1, D[d-1].V[kPrev-1], D[d-1].V[kPrev-1]+1-kPrev))
        {
            i++;
            x[i] = D[d-1].V[kPrev+1];
            y[i] = D[d-1].V[kPrev+1]-kPrev-1;
            kPrev = kPrev + 1;
        }
        else
        {
            i++;
            x[i] = D[d-1].V[kPrev-1];
            y[i] = D[d-1].V[kPrev-1]+1-kPrev;
            kPrev = kPrev - 1;
        }
        d--;
    } 
    output_result(x, y, i, A, B);
}
bool best_choice(int x1, int y1, int x2, int y2)
{
    if(x1 + y1 == x2 + y2)
        return x1 > x2;   //路径数一样，优先考虑删除，即x大的坐标
    else
        return x1 + y1 > x2 + y2;
}
void output_result(int x[], int y[], int n, vector<string> A, vector<string> B)
{
    int i = 0;
    int X = x[0], Y = y[0], XSTART = 0, YSTART = 0;  //记录连续的坐标
    vector<string> delete_result, insert_result;
    char s[4];
    while (XSTART < A.size() && YSTART < B.size() && !A[XSTART].compare(B[YSTART]))
        XSTART++, YSTART++;
    while(i < n)
    {
        while(X-1 >= x[i+1] && Y-1 >= y[i+1] && !A[X-1].compare(B[Y-1]))
            X -= 1, Y -= 1;
        while(X > x[i+1] && X > XSTART)  //优先考虑删除
            X -= 1, sprintf(s, "%4d", X+1), delete_result.push_back(string(s) + "  ->  " + A[X]);
        while (Y > y[i+1] && Y > YSTART)
            Y -= 1, sprintf(s, "%4d", Y+1), insert_result.push_back(string(s) + "  ->  " + B[Y]);
        i++;
    }
    for(i = delete_result.size()-1; i >= 0; i--)
        cout << "-" << "        " << delete_result[i] << endl;
    for(i = insert_result.size()-1; i >= 0; i--)
        cout << "+" << "        " << insert_result[i] << endl;
    vector<string> ().swap(delete_result);
    vector<string> ().swap(insert_result);
}
bool equal(vector<string> A, vector<string> B, int N)
{
    int i = 0;
    while (i < N && !A[i].compare(B[i])) i++;
    return i == N; 
}
